package leetcode.interviewClassics;

import leetcode.ListNode;

import java.util.HashSet;

/**
 * @author Cheng Jun
 * Description: 移除未排序链表中的重复节点。保留最开始出现的节点。
 * https://leetcode-cn.com/problems/remove-duplicate-node-lcci/
 * @date 2021/10/31 12:08
 */
public class removeDuplicateNodes {

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(1, null);
        ListNode listNode4 = new ListNode(2, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(3, listNode3);
        ListNode listNode1 = new ListNode(2, listNode2);
        ListNode listNode0 = new ListNode(1, listNode1);
        // removeDuplicateNodes(listNode0);


    }

    // Set 集合的add 判断是否能添加成功，
    static ListNode removeDuplicateNodes(ListNode head) {

        HashSet<Integer> set = new HashSet<>();
        ListNode currentNode = head;
        if (currentNode != null) {
            set.add(currentNode.val);
        } else {
            return head;
        }
        // 不能判断当前节点的值，存不存在，因为最后一个元素如果存在，怎么把倒数第二个元素的next 置为null？单向链表做不到。
        // 先存入第一个节点的val，然后判断当前节点的next的val 存不存在于set，不存在 就节点往后 移动一位，存在就移动两位。

        // next 不为null，才有比较的必要
        while (currentNode.next != null) {
            if (set.add(currentNode.next.val)) {
                currentNode = currentNode.next;
            } else {
                // 如果插入失败，就代表已经存在，那么就把当前节点的next 变为 下一个节点的next
                currentNode.next = currentNode.next.next;
            }
        }
        return head;
    }


}
